class Node:
    def __init__(self, val):
        self.val = val
        self.neighbors = {}
        self.count = 0


class Solution(object):
    def numMatchingSubseq(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: int
        """
        n = len(s)
        DP = [[-1 for _ in range(26)] for _ in range(n)]
        base = ord(s[-1]) - ord('a')
        DP[-1][base] = n - 1
        for i in range(n - 2, -1, -1):
            base = ord(s[i]) - ord('a')
            for j in range(26):
                if j == base:
                    DP[i][j] = i
                else:
                    DP[i][j] = DP[i + 1][j]
        tree = Node('#')
        for word in words:
            node = tree
            for c in word:
                if c not in node.neighbors:
                    new_node = Node(c)
                    node.neighbors[c] = new_node
                    node = new_node
                else:
                    node = node.neighbors[c]
            node.count += 1
        self.c = 0
        def search(node, id):
            self.c += node.count
            if id < n:
                for c in node.neighbors:
                    next_id = DP[id][ord(c) - ord('a')]
                    if next_id >= 0:
                        search(node.neighbors[c], next_id + 1)

        search(tree, 0)

        return self.c

data = Solution()
s = "abcde"
words = ["a", "bb", "acd", "ace"]
print(data.numMatchingSubseq(s, words))
